package leetcode;

import java.util.Arrays;

/**
 * @创建人 MBY381
 * @创建时间 2022/3/30 18:54
 * @描述 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 */
public class Solution213 {
    /**
     * 总体思路：
     * 此题是 198. 打家劫舍 的拓展版： 唯一的区别是此题中的房间是环状排列的（即首尾相接），而 198.198. 题中的房间是单排排列的；而这也是此题的难点。
     * 环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：
     * 在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]），最大金额是 p_1p1
     * 在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]），最大金额是 p_2p2
     * 综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)max(p1,p2) 。
     * <p>
     * <p>
     * 如果不偷窃最后一间房屋，则偷窃房屋的下标范围是 [0, n-2][0,n−2]；如果不偷窃第一间房屋，则偷窃房屋的下标范围是 [1, n-1][1,n−1]。
     *
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return Math.max(robWoRi(Arrays.copyOfRange(nums, 0, nums.length - 1)), robWoRi(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    public static int robWoRi(int[] nums) {
        int[] maxValue = new int[nums.length + 1];
        maxValue[0] = 0;
        maxValue[1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxValue[i + 1] = Math.max(maxValue[i], (maxValue[i - 1] + nums[i]));
        }
        return Math.max(maxValue[nums.length], maxValue[nums.length - 1]);
    }

    public static void main(String[] args) {

    }
}
